#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> hash;
        for (Node* cur = head; cur; cur = cur->next)
        {
            hash[cur] = new Node(cur->val);
        }
        for (Node* cur = head; cur; cur = cur->next)
        {
            if (cur->next)  hash[cur]->next = hash[cur->next];
            if (cur->random)  hash[cur]->random = hash[cur->random];
        }
        return hash[head];
    }
};